package com.github.kezhenxu94.playground.java.interview.didi;

import java.util.Arrays;
import java.util.BitSet;
import java.util.Scanner;

public class DDSubsetSum {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int len = sc.nextInt();
		int sum = sc.nextInt();
		int[] array = new int[len];
		for (int i = 0; i < len; i++)
			array[i] = sc.nextInt();
		if (currentSum(array, len - 1) < sum) {
			System.out.println(0);
		} else if (currentSum(array, len - 1) == sum) {
			System.out.println(1);
		} else {
			int[] result = new int[len];
			Arrays.sort(array);
			if (array[0] > sum) {
				System.out.println(0);
			} else {
				count = 0;
				backtracking(result, array, len, 0, sum, new BitSet());
				System.out.println(count);
			}
		}
		sc.close();
	}

	private static int count = 0;

	private static void backtracking(int[] result, int[] array, int len, int k, int destSum, BitSet chosen) {
		int lastChosen = chosen.previousSetBit(chosen.size());
		for (int i = lastChosen >= 0 ? lastChosen : 0; i < array.length; i++) {
			if (!chosen.get(i)) {
				chosen.set(i);
				result[k] = array[i];
				if (currentSum(result, k) == destSum) {
					count++;
				} else if (currentSum(result, k) > destSum) {
					break;
				} else if (k + 1 < len) {
					backtracking(result, array, len, k + 1, destSum, BitSet.valueOf(chosen.toByteArray()));
				}
			}
		}
	}

	private static int currentSum(int[] result, int k) {
		int sum = 0;
		for (int i = 0; i <= k; i++)
			sum += result[i];
		return sum;
	}
}
